package hanjia;

import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/6-下午1:46
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> results=new ArrayList<>();
        if (root==null) {
            return results;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size=queue.size();
            ArrayList<Integer> result = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                result.add(poll.val);
                if (poll.left!=null){
                    queue.offer(poll.left);
                }

                if (poll.right!=null){
                    queue.offer(poll.right);
                }
            }


            results.add(result);




        }


        return results;


    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> results=new ArrayList<>();
        if (root==null) {
            return results;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        int count=1;
        while (!queue.isEmpty()){
            int size=queue.size();
            LinkedList<Integer> result = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (count%2==1){
                    result.offerLast(poll.val);
                }else {
                    result.offerFirst(poll.val);
                }

                if (poll.left!=null){
                    queue.offer(poll.left);
                }

                if (poll.right!=null){
                    queue.offer(poll.right);
                }
            }


            results.add(result);
            count++;



        }


        return results;


    }


}
